Mathematical programming entails the modeling of some system with an objective function of appropriate system variables that is to be optimized according to an appropriate criterion. Mathematical programming also involves the maximization of some benefit or the minimization of some cost when specific values are assigned to the system decision variables, as well as the determination of optimal decision variables for multiple goals or other mathematical criteria. The function to be optimized is called the objective function. In such problems the decision variables are usually limited to those values in which other functions of the variables must satisfy mathematical equalities or inequalities modeling system restrictions. Each such restriction is called a constraint of the mathematical programming problem, which is sometimes constrained in other ways as well. The collection of such allowable values is called the feasible region of the problem.
Rudimentary mathematical optimization techniques were devised at least as early as Isaac Newton and the development of differential calculus. Mathematical programming is now a field in the mathematical sciences well-developed both theoretically and computationally, as described in such books as Nonlinear Programming: Theory and Algorithms by M. S. Bazaraa et al. (Reference 1), Introduction to Mathematical Programming: Applications and Algorithms by W. Winston et al. (Reference 2), and Model Building in Mathematical Programming by H. P. Williams (Reference 3).
A general mathematical programming problem with m inequality constraints can be stated as the following problem M, where the term “Equation” refers to any numbered mathematical object.maximize: f(x1, . . . ,xn)  (1)subject to: gi(x1, . . . ,xn)≦bi,i=1, . . . , m.  (2)
where:                the objective function is f(x1, . . . , xn) of Equation 1;        gi(x1, . . . , xn), i=1, . . . , m, of Equation 2 are functions;        bi, i=1, . . . , m, of Equation 2 are given constants; and        the constraints of M are the inequalities of Equation 2.Problem M may have no solution. This situation usually occurs either because there are no n-dimensional points (x1, . . . , xn) satisfying the constraints of Equation 2 or because the objective function of Equation 1 may be made arbitrarily large for points (x1, . . . , xn) satisfying the constraints of Equation 2.        
One application of solving M is the solution of sets of nonlinear equations or inequalites. For example, one may find a solution (x1*, . . . , xn*) to the set of nonlinear inequalities gi(x1, . . . , xn)≦bi, i=1, . . . , m, of Equation 2 by solving the following nonlinear problem in the n+m dimensional points (x1, . . . , xn+m):minimize: (xn+1)2+ . . . +(xn+m)2 subject to: gi(x1, . . . ,xn)+(xn+i)2=bi,i=1, . . . ,m. The optimal values x1*, . . . , xn* from the optimal solution (x1*, . . . , xn+m*) to this problem is a solution to the inequalities of Equation 2.
A simple mathematical programming problem with two decision variables x and y, objective function f(x,y)=x+y, and constraints x2+y2≧1, x2+y2≦2, x≧0, y≧0 ismaximize: f(x,y)=x+y subject to: x2+y2≧1;x2+y≦2;x≧0; andy≧0.The solution in the (x,y) plane is shown in FIG. 1, which is a graphical representation of the feasible region of a two-variable illustrative optimization problem with linear objective function in accordance with the prior art. FIG. 1 shows how the maximum value of the objective function is obtained at the values of the two variables where the objective function with its maximum value intersects the feasible region.
A simple mathematical programming problem with three decision variables (x,y,z); objective function f(x,y,z)=x+y; and constraints x2−y2+z2≦2, x2+y2+z2≦0 ismaximize: f(x,y,z)=xy+yz subject to: x2−y2+z2≦2; andx2+y2+z2≦10.The two solutions of the variables (x,y,z) are shown in FIG. 2, which is a graphical representation of the feasible region of a three-variable illustrative optimization problem with a nonlinear objective function in accordance with the prior art, at the points where the two twisted planes touch the dumbbell-shaped surface. FIG. 2 shows how the maximum value of the objective function is obtained at the values of the two variables where the objective function with its maximum value intersects the feasible region. In particular, FIG. 2 shows how a problem can have more than one optimal answer for the values of the variables even though the objective function value of all such answers will be the same.
The best known and most frequently used prior art in the field of mathematical programming is linear programming. A brief NPR story on its initial development can be heard at http://www.npr.org/templates/story/story.php?storyId=4661503.
A linear programming model minimizes or maximizes a linear objective function consisting of a sum of a given constant coefficient times each unknown variable. Each system restriction, or constraint, is also linear. In other words, it is a sum of a given constant coefficient times each unknown variable that is either equal, greater than or equal, or less than or equal to another coefficient. Each variable itself can either be any real number or required to be greater than or equal to zero or less than or equal to zero. In theory, any mathematical programming problem can be approximated to any degree of accuracy by a linear programming model, usually with an enormous number of constraints and variables for a sufficiently accurate approximation, as well as some of these variables further restricted to integer or binary (0 or 1) values.
Consider the general linear programming problem L below with objective function c1x1+ . . . +cnxn of Equation 3 and the constraints the inequalities of Equations 4-5:maximize: z=c1x1+ . . . +cnxn  (3)subject to: ai1x1+ . . . +ainxn≦bi,i=1, . . . ,m; and  (4)xj≧0,j=1, . . . , n.  (5)All linear programming problems can be put into this general form. The decision variable xj, j=1, . . . , n, might be the amount of product j (or activity j) requiring aij units of resource i to be produced (or allocated) when there are only bi, i=1, . . . , m, units of resource i available. The objective is to maximize the gain (or profit) c1x1+ . . . +cnxn, where cj, j=1, . . . , n, represents the profit per unit of product j. In any given problem L, the cj, aij and bi are known constants and the decision variables xj must be determined to maximize the total gain z, which is not a variable but standard notation for the objective function f(x1, . . . , xn). Problem L does not have a solution if either there are no points (x1, . . . , xn) satisfying the constraints of Equations 4-5 or the objective function of Equation 3 can be made arbitrarily large for (x1, . . . , xn) satisfying the constraints of Equations 4-5.
Problem L can be written in matrix form asmaximize: z=cTx subject to: Ax≦b; andx≧0.
where:                x is an n×1 vector of variables xj, j=1, . . . , n;        A is an m×n matrix [aij] with 1×n transposed rows                    aiT, i=1, . . . , m;                        b is an m×1 vector;        c is an n×1 vector; and        0 is an n×1 vector of zeros.The constraint aiTx≦bi determines a hyperplane, which is here the set of n-dimensional points {x: aiTx=bi}. Thus any feasible point x to problem L must lie in the closed half-space {x: aiTx≦bi}.        
Problem L is called the primal linear programming problem here. The dual linear programming problem DL of L can be written asminimize: w=bTy subject to: ATy≧c; andy≧0.
where:                y is an m×1 vector of variables;        AT is the transpose of the m×n matrix A of L with 1×m transposed columns (aj)T, j=1, . . . n;        b is an m×1 vector;        c is an n×1 vector; and        0 is an m×1 vector of zeros.The constraint (aj)Ty≧cj determines a hyperplane, which here is the set of m-dimensional points {y: (aj)Ty=cj}. Thus any feasible point y to problem DL must lie in the closed half-space {y: (aj)Ty≧cj}. From the duality theory of linear programming in Linear Programming and Network Flows by M. S. Bazaraa, et al. (Reference 4), an important relationship between the primal problem L and its dual DL is that if either has an optimal solution, then the optimal value z* of L equals the optimal w* of DL. In other words, the primal L can be solved by obtaining a solution to its dual DL.        
Similarly, there is a more complicated Lagrangian dual problem DM to the nonlinear primal problem M as discussed in Nonlinear Programming: Theory and Algorithms by M. S. Bazaraa et al. (Reference 1). DM reduces to DL for linear programming. More generally, when the function f(x1, . . . , xn) is concave, the functions gi(x1, . . . , xn), i=1, . . . , m, are convex as defined in Reference 1, and a solution exists to M, then the optimal objective function value for M equals that of DM. If any of the functions do not satisfy these properties but a solution to M exists, then the optimal objective function value for M may be smaller than that of DM.
A linear programming problem with two variables x1 and x2 ismaximize: z=3x1+5x2 subject to: x1≦4;x2≦6;3x1+2x2≦18; andx1,x2≧0.Its feasible region and solution are shown in FIG. 3, where the normals to the three hyperplanes determining the constraints of Equation 4 of L are the vectors a1=(1, 0)T, a2=(1, 0)T, and a3=(3, 2)T. The normal vector to the objective function of Equation 3 is c=(3, 5)T. Observe that the optimal point (2,6) is determined in this two-dimensional feasible region by the two constraints with normals a1 and a3, which are most nearly parallel c. FIG. 3 is a graphical representation of geometry of linear programming problems in accordance with the prior art. For a two-variable illustrative problem, it shows the extreme points (i.e., corners or vertices) of the feasible region and how the maximum value of the objective function is always obtained at an extreme point that is the point of intersection of the feasible region and the objective function at its maximum value.
In general, mathematical programming problems and linear programming problems model situations in real physical or abstract systems. The reason for solving these mathematical models is to obtain optimum values for the system decision variables. These optimal values are then used to construct or operate the underlying system that was modeled and hence to make significant real-world decisions.
A major proportion of all scientific computation is devoted to linear programming. As noted in Linear Programming 1: Introduction, G. B. Dantzig, et al. (Reference 5), the applications of linear programming arise in a broad range of technological, scientific, and industrial areas, including:
1. Resource allocation: optimal amounts of a resource allocated to different tasks;
2. Mixture selection: optimal oil mixtures or portfolio selection, for example;
3. Distribution: optimal amounts of commodities distributed to different locations;
4. Networks: optimal paths or flows or the construction of networks;
5. Game theory: the determination of optimal mixed strategies in two-person, zero-sum games, as well as other types of games.
6. Integer programming: linear programming problems with the additional requirement that some or all of the variables must have integer values, where the major computational step in the solution is linear programming;
7. Binary (0-1) integer programming: linear programming problems with the additional requirement that variables can have only the values 0 or 1 to model yes/no decisions, for example, where the major computational step in the solution is often linear programming;
8. Assignments: optimal assignment of item i to class j using 0-1 programming to maximize some benefit or minimize some cost, where a variable xij=1 if item i is assigned to class j and xij=0 otherwise;
9. The solution of a set of linear equations or inequalities by linear programming, particularly when the variables are required to be nonnegative;
10. The solution of linear Diophantine equations (i.e., linear equations in which the variables are required to be integers) by integer programming;
11. The approximate solution of M, and hence systems of nonlinear equations and inequalities, by approximating a nonlinear equation with many linear ones with additional variables and constraints (including 0-1 integer restrictions); and
12. The approximate solution of M, and hence systems of nonlinear equations and inequalities, by approximating a nonlinear surface by a set of discrete point in n dimensions along with additional variables and constraints, then using 0-1 or integer programming.
The significance of these applications is illustrated by the use of linear programming in Application 3, resource allocation, which refers to the optimal allocation of specific technological resources to achieve particular technological results. Examples include the scheduling of airline flights and the assignment of aircraft and crews to these flights, the determination of the product mix for a factory, and the deployment of military personnel and equipment. Factories use linear programming models for scheduling production and controlling inventory levels to satisfy product demand, as well as minimizing production and inventory costs. A communications system routes telephone traffic through a transmission network so demand is satisfied, no transmission links are overloaded, and transmission costs are minimized (Reference 6). Electricity is similarly dispersed. Large organizations such as military units or hospitals can minimize the cost of diet for soldiers or patients while satisfying nutritional requirements.
In linear programming application 11 listed above, nonlinear functions are linearized to obtain an approximate solution to a nonlinear mathematical programming problem. For example, FIG. 4 is a graphical representation of the approximation of a continuous function of one variable by a piecewise linear function to illustrate that linear programming can apply to nonlinear optimization problems in accordance with the prior art.
Linear programming has been studied for over sixty years. The best known prior art approach for solving L is the simplex algorithm, developed in the 1947 by Dantzig (Reference 7), provided the first effective solution procedure and remains the underlying algorithm used by many commercial linear programming and virtually all integer programming packages. It starts from some initial extreme point (i.e., corner or vertex) of the feasible region of L. The simplex method then proceeds on the exterior of the feasible region, which is a polytope as defined in Reference 4, from one extreme of the feasible region to another with a value of the objective function at least as good until an optimal extreme point is reached as depicted in FIG. 5, which is a graphical representation of the geometry in three variables of the prior art known as the simplex algorithm for solving the linear programming problem L with three variables. This algorithm starts at some extreme point of the feasible region. The method moves then along the exterior of the polytope defined by the problem's linear constraints from one extreme point to another, with the objective function never decreasing until an optimal extreme point is finally reached. Such an optimal extreme point is guaranteed if the problem has a solution. Unfortunately the computational complexity of the simplex method is not polynomial in the worst case, even though it exhibits polynomial complexity on average, as noted in References 4 and 5.
Khachian's ellipsoid algorithm (Reference 8) solves linear programming problems in polynomial time, but it performs poorly in practice. More recently, Dikin (References 9, 10), Karmarkar (Reference 11), and others developed a polynomial projection approach that evolved to various polynomial interior-point barrier-function methods (References 12-15) used in some large-scale applications. FIG. 6 is a graphical representation of the geometry of the prior art of interior-point algorithms for solving a linear programming problem L with two variables. An interior-point algorithm starts at some interior point of the feasible region (i.e., the polytope defined by problem's linear constraints). It then proceeds from one interior point to another in the interior of the feasible region with the objective function increasing until an optimal solution is obtained on the exterior of the polytope. This optimal solution may not be an extreme point. However, an optimal extreme point with the same optimal value of the objective function can be obtained by a further process called the “crossover” step.
In contrast to the simplex method, interior-point methods do not allow efficient post-optimality analysis for solving the binary and integer linear programming problems of most industrial applications. Such binary and integer problems are NP-hard. In other words, no polynomial algorithm has been found to solve general binary and integer linear programming problems. This fact means that no solution to large problems of this type has been heretofore achieved in a sufficiently small computation time to approach “real time” in a commercial sense.
Solving such binary and integer linear programming models represent the principal computational use of linear programming, so simplex methods remain the dominant approach. However, there is no single best algorithm for solving L. For any current method, we can always formulate an instance of problem L for which the method performs poorly (References 13, 14). As a result, there is a need for a system, method and apparatus for more efficiently allocating resources via linear programming.